package com.study.sort;

/**
 * - *@ClassName HeapSort
 * - *@Author LiuHuaBing
 * - *@Date 2021/12/15 15:18
 * - *@Version 1.0
 * - 堆排序
 */
public class HeapSort {


    public static void main(String[] args) {
        int arr[] = {9, 5, 4, 8, 6, 2, -5, 93, 4};
        arr = heapSort(arr);
        for (int i : arr) {
            System.out.println(i);
        }
    }


    private static int[] heapSort(int[] arr) {
        // 将数组按照大跟堆的规则重组
        for (int i = 0; i < arr.length; i++) {
            heapInsert(arr, i);
        }
        // 将大根堆依次拆除顶级元素
        for (int i = arr.length; i > 0; i--) {
            heapify(arr, 0, i);
        }

        return arr;

    }


    private static void heapInsert(int[] arr, int index) {
        while ((index - 1) / 2 >=0) {
            int parentIndex = (index - 1) / 2;
            if (arr[index] > arr[parentIndex]) {
                swap(arr, index, parentIndex);
                index = parentIndex;
            } else {
                break;
            }
        }
    }

    private static void heapify(int[] arr, int index, int heapSize) {
        swap(arr, index, heapSize - 1);
        heapSize--;
        int largestIndex;
        while (index*2+1 < heapSize-1) {
            int left = index * 2 + 1;
            //有左右孩子
            if (left+1<heapSize-1){
                if (arr[left] >= arr[left + 1] && arr[left] > arr[index]) {
                    largestIndex = left;
                    swap(arr, index, largestIndex);
                    index =left;
                } else if (arr[left] < arr[left + 1] && arr[left + 1] > arr[index]) {
                    largestIndex = left + 1;
                    swap(arr, index, largestIndex);
                    index =left+1;
                } else {
                    break;
                }
            }else {
                if (arr[left] > arr[index]) {
                    largestIndex = left;
                    swap(arr, index, largestIndex);
                    index =left;
                }  else {
                    break;
                }

            }
        }
    }


    private static void swap(int[] arr, int index1, int index2) {
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
}
